# -*- coding: utf-8 -*-
'''
flexp is a experiment data processing program, it analyze testcase
execution trace and transfer the data to other format in order to
do futher analysis.
'''
__author__ = 'He Li'
__version__ = 0.9
__copyright__ = "Copyright 2008-6, Sei Peking University"
__license__ = "Apache 2.0"
_debug = 0

import sys
sys.path.append('src')
sys.path.append('test')
import re
import os
import random
import math
from itertools import groupby
from util.stringutils import chomp
from os import path
from heapq import heapify, heappop, heappush
from util.log4p import logger
import BitVector
import types

import traceback
Log = logger()

class SSelectionException(Exception):
    pass

class TestCase:
    '''
        This class represents a TestCase object which has following attr:
        1> testcase id
        2> all the statemenst executed by this testcase(grouped by statement number)
        3> whether this testcase is positive
    '''
    def __init__(self, statement_size , seq = None, positive = None):
        self.seq = seq
        self.statements = BitVector.BitVector(size = statement_size)
        self.positive = positive


file_name_pattern = re.compile(r'(out)(\d+)\.txt|(code)_([tf])\.txt')
class Program:
    '''
        This class represents a testcase execution trace of a specific version
        of a program, with following attr:
        1> program version
        2> all positive testcases
        3> all negative testcases
        4> path of this program
        5> name of this program
        6> fault statements specified in fault.txt
    '''
    def __init__(self, name, version, path=None, faults =[], exec_context = None):
        self.version = version
        self.positive_testcases = []
        self.negative_testcases = []
        self.path = path
        self.name = name
        self.faults = faults
        self.exec_context = exec_context
        self.start_seq = -1
        self.end_seq = -1

        if path == None or path == '': return
        self.load(path)

    def load(self, program_path):
        '''
            load program from file system, a program directory must contain these
            files:
            1> out1.txt or code_t.txt
            2> out2.txt or code_f.txt
        '''
        self.path = program_path
        # retrieve all .txt files under this directory
        for file in filter(lambda x : os.path.splitext(x)[1] == '.txt', \
            os.listdir(program_path)):
            if not file.startswith('out') and not \
                file.startswith('code'):
                continue;
            # parse file name according to file name pattern
            file_info = filter(lambda x : x != None, \
                file_name_pattern.match(file).groups())

            # select testcase generator
            testcase_iterator = {
                'out':out_testcase_iterator,
                'code':code_testcase_iterator
            }[file_info[0]]

            # select testcase container(positive or negative)
            testcases = {
                '1':self.positive_testcases,
                '2':self.negative_testcases,
                't':self.positive_testcases,
                'f':self.negative_testcases
            }[file_info[1]]

            # iterate through all testcass in testcase files
            for testcase in testcase_iterator(os.path.join(program_path, file), {\
                '1':True, \
                '2':False, \
                't':True, \
                'f':False}[file_info[1]], self.start_seq, self.end_seq):
                testcases.append(testcase)

    def select(self, N, J, M, testcases):
        '''
            testcase selection generator,generated result contains two parts:
            1> generate sequence number
            2> testcase set
        '''
        S = []
        len_testcases = len(testcases)
        pivot = N
        while pivot <= len_testcases:
            pivot += M
        # j in [0,J), x in [N,min(len(self.testcases),N+J*M))
        for (j, x) in zip(range(J), range(N, pivot, M)):
            # one pass testcase set selection
            if j == 0:
                if N > len_testcases: N = len_testcases
                # random select a testcase from negative testcases
                neg_index = -1
                for i in range(len(testcases)):
                    if not testcases[i].positive:
                        neg_index = i
                        break
                if neg_index < 0:
                    raise SSelectionException()
                neg_index = random.randint(neg_index, len(testcases)-1)
                S.append(testcases[neg_index])
                del testcases[neg_index]
                # select other N-1 testcases from all testcases
                S += self.__selectn(testcases, N - 1)
            else:
                if x > len_testcases: M = (len_testcases - N) % M
                S += self.__selectn(testcases, M)
            yield (j, S)

    def create_file(self, *args, **keywords):
        '''
           crete output file, if output file exists, then
           use append mode
        '''
        # processing options
        enable_array_output = False
        for k, v in keywords.iteritems():
            if k == 'enable_array_output' and v:  enable_array_output = True

        handles = []
        for handle in args:
            # if array output is disabled, just return None
            if enable_array_output:
                if not self.exec_context.enable_array_output():
                    handles.append(None)
                    continue
            # output path is like: output_directory/program_name/version/handle_name
            program_path = os.path.join(self.output_directory, self.name)
            if not os.path.exists(program_path):
                os.mkdir(program_path)
            version_path = os.path.join(program_path, self.version);
            if not path.exists(version_path):
                os.mkdir(version_path)
            file_handle = path.join(version_path, handle)

            # if file exists, append to it
            if os.path.exists(file_handle):
                handles.append(open(file_handle, 'wa'))
            else:
                handles.append(open(file_handle, 'w'))
        return tuple(handles)

    def close_file(self, *args):
        '''
            close all files
        '''
        for file_handle in args:
            if file_handle != None and type(file_handle) == file:
                file_handle.close()

    def proc(self, output_directory, T, N, M, J):
        '''
            processing entry point, i do all these things:
            1> compute statements vector(contains seq number of statements which
            requires suspicions computation)
            2> create and init output files
            3> using testcase selection generator, generate testcase set and call
            reduce to do the math
            4> organize output
        '''
        self.output_directory = output_directory
        # init random lib
        random.seed()

        try:
            # create and prepare all output files
            block1_size_doc, block2_size_doc, block1_avg_size_doc, block2_avg_size_doc, \
                tarantula_finding_expense_doc, tarantula_block_expense_doc, CBI_finding_expense_doc, CBI_block_expense_doc, \
                Jaccard_finding_expense_doc, Jaccard_block_expense_doc, Ochiai_finding_expense_doc, Ochiai_block_expense_doc, \
                SAFL_finding_expense_doc, SAFL_block_expense_doc, block1_vec_doc, block2_vec_doc =  \
                self.create_file('block1_size_doc.txt', 'block2_size_doc.txt', 'block1_avg_size_doc.txt', \
                'block2_avg_size_doc.txt', 'tarantula_finding_expense_doc.txt', 'tarantula_block_expense_doc.txt', \
                'CBI_finding_expense_doc.txt', 'CBI_block_expense_doc.txt', 'Jaccard_finding_expense_doc.txt', \
                'Jaccard_block_expense_doc.txt', 'Ochiai_finding_expense_doc.txt', 'Ochiai_block_expense_doc.txt', \
                'SAFL_finding_expense_doc.txt', 'SAFL_block_expense_doc.txt', 'block1_vec_doc.txt', 'block2_vec_doc.txt')

            block1_size_array, block2_size_array, block1_avg_size_array, block2_avg_size_array, \
                tarantula_finding_expense_array, tarantula_block_expense_array, CBI_finding_expense_array, CBI_block_expense_array, \
                Jaccard_finding_expense_array, Jaccard_block_expense_array, Ochiai_block_expense_array, Ochiai_finding_expense_array, \
                SAFL_finding_expense_array, SAFL_block_expense_array, block2_vec_array, block1_vec_array = \
                self.create_file('block1_size_array.txt', 'block2_size_array.txt', 'block1_avg_size_array.txt', \
                'block2_avg_size_array.txt', 'tarantula_finding_expense_array.txt', 'tarantula_block_expense_array.txt', \
                'CBI_finding_expense_array.txt', 'CBI_block_expense_array.txt', 'Jaccard_finding_expense_array.txt', \
                'Jaccard_block_expense_array.txt', 'Ochiai_block_expense_array.txt', 'Ochiai_finding_expense_array.txt', \
                'SAFL_finding_expense_array.txt', 'SAFL_block_expense_array.txt', 'block2_vec_array.txt', \
                'block1_vec_array.txt', enable_array_output=True)

            # put suspision calc output file in a map in order to simplify
            # the process due to the similarity of operations on these output files
            suspicion_files = {'tarantula':(tarantula_finding_expense_doc, \
                    tarantula_finding_expense_array, tarantula_block_expense_doc, \
                    tarantula_block_expense_array),
                    'CBI':(tarantula_finding_expense_doc, \
                tarantula_finding_expense_array, tarantula_block_expense_doc, \
                tarantula_block_expense_array),
                    'Jaccard':(Jaccard_finding_expense_doc, \
                Jaccard_finding_expense_array, Jaccard_block_expense_doc, \
                Jaccard_block_expense_array),
                    'Ochiai':(Ochiai_finding_expense_doc, \
                Ochiai_finding_expense_array, Ochiai_block_expense_doc, \
                Ochiai_block_expense_array),
                    'SAFL':(SAFL_finding_expense_doc, \
                SAFL_finding_expense_array, SAFL_block_expense_doc,
                SAFL_block_expense_array)}

            if self.exec_context.enable_array_output():
                for v in suspicion_files.values():
                    v[1].write('{\n')
                    v[3].write('{\n')

            # start the calc process
            for i in range(T): # repeat T times
                # use this vector to record block1 size for each iteration
                block1_size_vec = []
                # use this vector to record block2 size for each iteration
                block2_size_vec = []
                # use this vector to record avg block1 element size for each iteration
                block1_avg_size_vec = []
                # use this vector to record avg block2 element size for each iteration
                block2_avg_size_vec = []
                # use this map of vector to record finding expense for each iteration
                suspicions_finding_expsenses ={'tarantula':[], 'CBI':[], \
                    'Jaccard':[], 'Ochiai':[], 'SAFL':[]}
                # use this map of vector to record block expense for each iteration
                suspicions_block_expenses = {'tarantula':[], 'CBI':[], \
                    'Jaccard':[], 'Ochiai':[], 'SAFL':[]}
                # use this vector to record individual block1 element size vector for
                # each iteration
                block1_vec_vec = []
                # use this vector to record individual block2 element size vector for
                # each iteration
                block2_vec_vec = []

                total_expense = 0.0
                S = []

                # merge all testcases
                testcases = list(self.positive_testcases) + \
                    list(self.negative_testcases)

                # iterate each testcase set generated by testcase generator
                for j, Sj in self.select(N, J, M, testcases):
                    Log.debug('iteration variables:version=%s,T=%d,j=%d,N=%d,J=%d,M=%d,len(testcases)=%d' \
                        % (self.version, i, j, N, J, M, len(testcases)))

                    # compute statement vector
                    statements_vector = _statements_vector(Sj)
                    # call reduce to calc results,which contains 3 parts
                    # 1, block size for each sub-block in block1 set
                    # 2, block size for each sub-block in blcok2 set
                    # 3, a map of expense for each metrics
                    block1_vec, block2_vec, expenses = \
                        self.reduce(Sj, statements_vector)
                    #print block1_vec
                    #print block2_vec

                    # process and record the result in data structures
                    block1_size_vec.append(len(block1_vec))
                    block2_size_vec.append(len(block2_vec))

                    block1_avg_size_vec.append(\
                        sum(map(lambda x : len(x), block1_vec))/float(len(block1_vec)))
                    #print block1_avg_size_vec
                    block2_avg_size_vec.append(\
                        sum(map(lambda x : len(x), block2_vec))/float(len(block2_vec)))

                    for k, v in expenses.iteritems():
                        suspicions_finding_expsenses[k].append(v[0])
                        suspicions_block_expenses[k].append(v[1])
                    block1_vec_vec.append(','.join(map(lambda x : str(len(x)), block1_vec)))
                    block2_vec_vec.append(','.join(map(lambda x : str(len(x)), block2_vec)))

                # generate output
                for j, s in enumerate(block1_size_vec):
                    block1_size_doc.write('%d:%f\n'%(j, s))
                for j, s in enumerate(block2_size_vec):
                    block2_size_doc.write('%d:%f\n'%(j, s))
                for j, s in enumerate(block1_avg_size_vec):
                    block1_avg_size_doc.write('%d:%f\n'%(j, s))
                for j, s in enumerate(block2_avg_size_vec):
                    block2_avg_size_doc.write('%d:%f\n'%(j, s))
                for j, s in enumerate(block1_vec_vec):
                    block1_vec_doc.write('%d:%s\n'%(j, s))
                for j, s in enumerate(block2_vec_vec):
                    block2_vec_doc.write('%d:%s\n'%(j, s))

                for k, v in suspicions_finding_expsenses.iteritems():
                    for j, s in enumerate(v):
                        suspicion_files[k][0].write('%d:%f\n'%(j, s))

                for k, v in suspicions_block_expenses.iteritems():
                    for j, s in enumerate(v):
                        suspicion_files[k][2].write('%d:%f\n'%(j, s))

                if self.exec_context.enable_array_output():
                    block1_size_array.write('{%s},\n'%(','.join(map(lambda x : str(x), block1_size_vec))))
                    block2_size_array.write('{%s},\n'%(','.join(map(lambda x : str(x), block2_size_vec))))

                    block1_avg_size_array.write('{%s},\n'%(\
                        ','.join(map(lambda x : str(x), block1_avg_size_vec))))
                    block2_avg_size_array.write('{%s},\n'%(\
                        ','.join(map(lambda x : str(x), block2_avg_size_vec))))

                    block1_vec_array.write(('{'+(','.join(['{%s}']*len(block1_vec_vec)))+'}')\
                        % tuple(block1_vec_vec))
                    block2_vec_array.write(('{'+','.join(['{%s}']*len(block2_vec_vec))+'}') \
                        % tuple(block2_vec_vec))

                    for k, v in suspicions_finding_expsenses.iteritems():
                        suspicion_files[k][1].write('{%s},'%(','.join(map(lambda x : str(x), v))))

                    for k, v in suspicions_block_expenses.iteritems():
                        suspicion_files[k][3].write('{%s},'%(','.join(map(lambda x : str(x), v))))

            if self.exec_context.enable_array_output():
                for v in suspicion_files.values():
                    v[1].write('},\n')
                    v[3].write('},\n')
        finally:
            try:
                self.close_file(block1_size_doc, block1_size_array, block2_size_doc, \
                    block2_size_array, block1_avg_size_doc, block1_avg_size_array, \
                    block2_avg_size_doc, block2_avg_size_array, tarantula_finding_expense_doc, \
                    tarantula_finding_expense_array, tarantula_block_expense_doc, tarantula_block_expense_array, \
                    CBI_finding_expense_doc, CBI_finding_expense_array, CBI_block_expense_doc, \
                    CBI_block_expense_array, Jaccard_finding_expense_doc, Jaccard_finding_expense_array, \
                    Jaccard_block_expense_doc, Jaccard_block_expense_array, Ochiai_finding_expense_doc, \
                    Ochiai_finding_expense_array, Ochiai_block_expense_doc, Ochiai_block_expense_array, \
                    SAFL_finding_expense_doc, SAFL_finding_expense_array, SAFL_block_expense_doc, \
                    SAFL_block_expense_array, block1_vec_doc, block1_vec_array, block2_vec_doc, \
                    block2_vec_array)
            except :
                stacktrace = traceback.format_exc()
                print stacktrace
                pass

    def __selectn(self, testcases, N):
        '''
            randomly select n testcase from given testcases
        '''
        selection = []
        # if testcase size is samller than N, just return it
        if len(testcases) <= N:
            selection += testcases
            del testcases[0:-1]
        else:
            # generate a random number in [k,l) for each iteration
            # where k in [0,N),l in [0,len(testcases))
            for (k, l) in zip(range(N), reversed(range(len(testcases)))):
                seed = random.randint(0, l)
                selection.append(testcases[seed])
                del testcases[seed]
        return selection

    def reduce(self, S, statements_vector):
        '''
            calc intermediate result
        '''
        # compute totalpassed,totalfailed,totalexpense, and collection all
        # statements
        statements = []
        totalfailed = 0.0
        totalpassed = 0.0
        total_expense = self.exec_context.total_expense(S)
        for testcase in S:
            if testcase.positive: totalpassed += 1
            else: totalfailed += 1
            for seq, hit in enumerate(testcase.statements):
                if hit > 0: statements.append((seq, testcase.seq, testcase.positive))

        # sort statements according to statement seq and testcase seq
        def statement_cmp(x, y):
            if x[0] == y[0]:
                return cmp(x[1], y[1])
            return cmp(x[0], y[0])
        statements.sort(cmp=statement_cmp)

        # record block1, block2, and odds for each statement
        block1s = {}
        block2s = {}
        odds = {}
        for k, g in groupby(statements, key=lambda x: x[0]):
            group = list(g)
            # compute block1,key for block1 is all seq number of testcases
            # which has executed the statement
            key1 = reduce(lambda x, y : ','.join([str(x), str(y)]), \
                unique(map(lambda x : x[1], group)))
            if key1 in block1s :
                block1s[key1].append(k)
            else:
                block1s[key1] = [k]

            # compute block2, is positive and negative number of testcases
            # which has executed the statement
            positive = 0
            negative = 0
            for stat_seq, testcase_seq, f in group:
                if f : positive += 1
                else : negative += 1

            key = ','.join([str(positive), str(negative)])
            if key in block2s:
                block2s[key].append(k)
            else:
                block2s[key] = [k]
            odds[k] = (float(positive), float(negative))

        expenses = {}
        # statement vector could be empty, because there is a possibility that
        # not one of the statements in statement vector has been executed by
        # negative testcases
        if len(statements_vector) == 0:
            expenses["tarantula"] = (0.0, 0.0)
            expenses['CBI'] = (0.0, 0.0)
            expenses['Jaccard'] = (0.0, 0.0)
            expenses['Ochiai'] = (0.0, 0.0)
            expenses['SAFL'] = (0.0, 0.0)
        else:
            # turantula finding_expense and block_expense
            finding_expense, block_expense =  self.suspicion_template(\
                self.tarantula, statements_vector, odds, totalfailed, \
                totalpassed, S, total_expense)
            expenses["tarantula"] = (finding_expense, block_expense)

            # CBI finding_expense and block_expense
            finding_expense, block_expense = self.suspicion_template(\
                self.CBI, statements_vector, odds, totalfailed, totalpassed, \
                S, total_expense)
            expenses["CBI"] = (finding_expense, block_expense)

            # Jaccard finding_expense and block_expense
            finding_expense, block_expense = self.suspicion_template(\
                self.Jaccard, statements_vector, odds, totalfailed, totalpassed, \
                S, total_expense)
            expenses["Jaccard"] = (finding_expense, block_expense)

            # Ochiai finding_expense and block_expense
            finding_expense, block_expense = self.suspicion_template(\
                self.Ochiai, statements_vector, odds, totalfailed, totalpassed, \
                S, total_expense)
            expenses["Ochiai"] = (finding_expense, block_expense)

            # SAFL finding_expense and block_expense
            finding_expense, block_expense = self.suspicion_template(\
                self.SAFL, statements_vector, odds, totalfailed, totalpassed, \
                S, total_expense)
            expenses["SAFL"] = (finding_expense, block_expense)

        return (block1s.values(), block2s.values(), expenses)

    def suspicion_template(self, suspicion_func, statements_vector, odds, \
        totalfailed, totalpassed, S, total_expense):
        #print str(suspicion_func)
        # apply suspicion function
        ss_tuple = zip(map(lambda x: x + self.start_seq, statements_vector), \
            apply(suspicion_func, [statements_vector, odds, totalfailed, totalpassed, S]))

        if len(ss_tuple) > 0 and type(ss_tuple[0][1]) != float:
            def tarantula_sus_sort(x, y):
                if x[1][0] == y[1][0]:
                    return cmp(y[1][1], x[1][1])
                return cmp(y[1][0], x[1][0])
            sus_cmp = tarantula_sus_sort
        else:
            sus_cmp = lambda x, y: cmp(y[1], x[1])

        # sort by suspicion in desendent order
        ss_tuple.sort(cmp=sus_cmp)
        # select suspicion tuple for fault statements defined in fault.txt

        #print total_expense,ss_tuple
        faults_tuple = [t for t in ss_tuple if t[0] in self.faults]
        if len(faults_tuple) == 0:
            Log.debug('faults tuple not found in suspicion calc results, will use 0.0 instead')
            max_threshold = 0.0
        else :
            max_threshold = max([t[1] for t in faults_tuple])

        # select statements whose supsicion is greater than min_threshold
        # and calculate finding_expense
        finding_expense = len(filter(lambda x:x[1] >= max_threshold, ss_tuple))
        finding_expense /= total_expense

        block_expense = float(len(filter(lambda x:x[1] == max_threshold, \
            ss_tuple)))
        return (finding_expense, block_expense)

    def tarantula(self, statements_vector, odds, totalfailed, totalpassed, \
         *others):
        assert totalfailed != 0
        def suspicion(s):
            if s not in odds: return 0.0
            dominator = (odds[s][1]/totalfailed) + \
                (odds[s][0]/totalpassed)
            if dominator == 0: return 1.0
            sup = (odds[s][1]/totalfailed)/dominator
            cof = max(odds[s][1]/totalfailed, odds[s][0]/totalpassed)
            return (sup, cof)
        if totalpassed == 0:
            return [1.0] * len(statements_vector)
        return [suspicion(x) for x in statements_vector]

    def CBI(self, statements_vector, odds, *others):
        def suspicion(s):
            if s not in odds: return 0.0
            return odds[s][1]/(odds[s][0] + odds[s][1])
        return [suspicion(x) for x in statements_vector]

    def Jaccard(self, statements_vector, odds, totalfailed, *others):
        if totalfailed == 0.0:
            return [0.0] * len(statements_vector)
        def suspicion(s):
            if s not in odds: return 0.0
            return odds[s][1]/(totalfailed + odds[s][0])
        return [suspicion(x) for x in statements_vector]

    def Ochiai(self, statements_vector, odds, totalfailed, *others):
        if totalfailed == 0:
            return [0.0] * len(statements_vector)
        def suspicion(s):
            if s not in odds: return 0.0
            return odds[s][1]/math.sqrt(totalfailed * \
                (odds[s][0] + odds[s][1]))
        return [suspicion(x) for x in statements_vector]

    def SAFL(self, statements_vector, odds, *others):
        # testcases is the last argument,stupid trick
        for arg in others: S = arg
        # compute matrix row size which is statement size
        m = max(map(lambda x: len(x.statements), S))
        # n is size of testcases
        n = len(S)

        # init a T * (m + 1) matrix(T is the number of testcases)
        E = []
        F = []
        for i, testcase in enumerate(S):
            # all statements that is excuted is marked 1
            erow = map(lambda x: float(x), testcase.statements)
            # mark positive testcases
            erow.append(testcase.positive and 1.0 or 0.0)
            E.append(erow)

            # compute sum of this row from E
            v = sum(erow[0:-1])
            frow = []
            for j in range(m):
                # set F[i][j] = 1/sum_{0}^{m}E_{i,k}
                if erow[j] > 0.0: frow.append(1/v)
                else: frow.append(0.0)
            F.append(frow)

        # compute suspisions for each statement in statement vector
        suspicions = []
        for j in statements_vector:
            numerator = sum([max([0.0]+[F[i][k] for i in range(0, n)
                if E[i][j] > 0.0 and E[i][m] == 0.0]) \
                    for k in range(0, m)])
            dominator = sum(max([0.0] + [F[i][k] for i in range(0, n) \
                if E[i][j] > 0]) \
                    for k in range(0, m))
            if dominator == 0.0: suspicions.append(0.0)
            else: suspicions.append(numerator/dominator)

        return suspicions

def _statements_vector(testcases):
    if len(testcases) == 0:
        return None
    vector = None
    for testcase in testcases:
        if type(vector) == types.NoneType: vector = testcase.statements
        else: vector = vector | testcase.statements
    sv = []
    for i, bit in enumerate(vector):
        if bit > 0: sv.append(i)
    return sv

out_testcase_pattern = re.compile(r'O:(?P<seq>\d+)')
out_statement_pattern = re.compile(r'A\.(\d+)')
def out_testcase_iterator(path, positive, start_seq, end_seq):
    '''
        parse out1.txt and out2.txt line by line
    '''
    out_file = open(path, 'r')
    iterator = iter(out_file)
    size = end_seq - start_seq + 1
    try:
        for line in iterator:
            line = chomp(line)
            if line.startswith('O'):
                match = out_testcase_pattern.match(line)
                testcase = TestCase(size, int(match.group('seq')), positive)
            else:
                seqs = map(lambda x: int(x), out_statement_pattern.findall(line))
                seqs.sort()
                for k, g in groupby(seqs):
                    testcase.statements[k - start_seq] = 1
                yield testcase
    finally:
        out_file.close()

code_statement_pattern = re.compile(r'(?P<seq>\d+)\((?P<rep>\d+|#):?\)')
def code_testcase_iterator(path, positive, start_seq, end_seq):
    '''
        parse code_t.txt and code_f.txt line by line
    '''
    code_file = open(path, 'r')
    iterator = iter(code_file)
    counter = 0
    size = end_seq - start_seq + 1
    try:
        for line in iterator:
            testseq, sepr, stms = chomp(line).partition(':')
            testcase=TestCase(size, int(testseq), positive)
            for s in filter(lambda x:len(x)>0, stms.split(',')):
                match = code_statement_pattern.match(s)
                seq = int(match.group('seq')) - start_seq
                repv = match.group('rep')
                if repv == '#': rep = 0
                else: rep = int(repv)
                if rep > 0: testcase.statements[seq] = 1
            counter += 1
            if counter % 100 == 0:
                Log.debug('already load %d testcases' %(counter))
            yield testcase
    finally:
        code_file.close()
    Log.debug('all load %d testcases' % (counter))

def fault_iterator(path):
    '''
        parse fault.txt using a hand-coded FSM
    '''
    fault_file = open(path, 'r')
    iterator = iter(fault_file)
    program_name = ''
    statement_buffer = ''
    statements = []
    version = 1
    try:
        buffer = "".join(fault_file.readlines())
        state = 0
        for i, c in enumerate(buffer):
            if c.isspace(): continue
            if state == 0:
                if c.isalnum() or c == '_': program_name += c
                elif c == ':': state = 1
            elif state == 1:
                if c == '{': state = 2
                elif c == ';':
                    state = 0
                    version = 1
                    program_name = ''
            elif state == 2:
                if c == '{': state = 3
                elif c == '}' or c == ',':
                    state = c == '}' and 1 or 2
                    version_name = 'v'+str(version)
                    version += 1
                    yield Program(program_name.lower(), version_name, '', statements)
                    statements = []
            elif state == 3:
                if c.isalnum(): statement_buffer += c
                elif c == ',':
                    statements += __to_statement(statement_buffer)
                    statement_buffer = ''
                elif c == '}':
                    statements += __to_statement(statement_buffer)
                    statement_buffer = ''
                    state = 2
    finally:
        fault_file.close()

def unique(inlist, sort=False, keepstr=True):
    typ = type(inlist)
    if not typ == list:
        inlist = list(inlist)
    if sort: inlist.sort()
    i = 0
    while i < len(inlist):
        try:
            del inlist[inlist.index(inlist[i], i + 1)]
        except:
            i += 1
    if not typ in (str, unicode):
        inlist = typ(inlist)
    else:
        if keepstr:
            inlist = ''.join(inlist)
    return inlist

def __to_statement(statement_buffer):
    if statement_buffer == 'none' or statement_buffer == '':
        return []
    else:
        return [int(statement_buffer)]

class ExecContext(object):
    def __init__(self, options):
        self.options = options
    def total_expense(self, S):
        if hasattr(options, 'total_expense'):
            if options.total_expense == 'avg':
                return self.__neg_testcase_avg_stat_total_expense(S)
            elif options.total_expense == 'sum':
                return self.__sum_stat_total_expense(S)
            else:
                return float(options.total_expense)
        else:
            return self.__neg_testcase_avg_stat_total_expense(S)

    def enable_array_output(self):
        if not hasattr(options, 'enable_array_output'):
            return True
        return options.enable_array_output

    def __neg_testcase_avg_stat_total_expense(self, S):
        total_expense = 0.0
        totalfailed = 0.0
        for testcase in S:
            if not testcase.positive:
                totalfailed += 1
                total_expense += len(testcase.statements)
        return total_expense / totalfailed

    def __sum_stat_total_expense(self, S):
        return len(_statements_vector(S))

class Stats(object):
    def __init__(self):
        self.data = {}
    def add(self, line):
        program, version, range= tuple(line.split(','))
        start, end = tuple(map(lambda x: int(x), range.split('-')))
        self.data[program+'_'+version] = \
            (program, version, start, end)

    def get(self, program, version):
        return self.data[program+'_'+version]

if __name__ == '__main__':
    import optparse
    from os import path
    parser = optparse.OptionParser()
    parser.add_option('-i', '--input-directory', dest='input_directory', help='''
        input directory at where programs exist
    ''')
    parser.add_option('-o', '--output-direcotry', dest='output_directory', \
        help='''output directory to place program output
    ''')

    parser.add_option('-p', '--program', dest='program', default='-', help='''
        specifiy which program to process,default will process all programs
        under the input directory
    ''')

    parser.add_option('-t', '--total-expense', dest='total_expense', default='avg', \
        help="how to calc total expense(avg,sum,float number)")

    parser.add_option('-a', '--enable-array-output', dest='enable_array_output', \
        action='store_false', default=True, help='enable array output(default is true)')

    parser.add_option('-T', '--iteration', dest='T', help='''
        time of iteration
    ''')
    parser.add_option('-N', '--initsize', dest='N', help='''
        initial testcase selection size
    ''')
    parser.add_option('-M', '--step', dest='M', help='''
        testcase selection step
    ''')
    parser.add_option('-J', '--size', dest='J', help='''
        testcase set size
    ''')

    options, args = parser.parse_args()
    programs = [i.lower() for i in os.listdir(options.input_directory) \
        if path.isdir(path.join(options.input_directory, i))]
    if options.program != '-':
        specified_programs = options.program.split(',')
        programs = filter(lambda x : x in specified_programs, programs)

    exec_context = ExecContext(options)

    if len(programs) == 0:
        Log.debug('''You have to at least provide a program name or there is no
            program under the input directory
        ''')
        sys.exit(2)
    try:
        if not os.path.exists(options.output_directory):
            os.mkdir(options.output_directory)

        stats = Stats()
        stat_file_path = path.join(options.input_directory, 'stat.txt')
        stat_file = open(stat_file_path)
        for i in iter(stat_file):
            stats.add(chomp(i))

        fault_file_path = path.join(options.input_directory, 'fault.txt')

        # iterate results from fault.txt
        for program in fault_iterator(fault_file_path):
            program.exec_context = exec_context
            # ignore programs which contains no fault statement
            if len(program.faults) == 0: continue
            if program.name in programs:
                program_path = os.path.join(\
                    os.path.join(options.input_directory, program.name), \
                        program.version)
                if not os.path.exists(program_path):
                    continue

                p, v, s, e = stats.get(program.name, program.version)
                program.start_seq = s
                program.end_seq = e
                Log.debug('processing program=%s,version=%s,start=%d, end=%d' % (program.name, program.version, s, e))

                program.load(program_path)
                try:
                    program.proc(options.output_directory, int(options.T), int(options.N), \
                        int(options.M), int(options.J))
                except SSelectionException, e:
                    Log.debug("There is a problem encountered when running selection process, \
                        no negtive testcase can be selected when j = 0")
    except Exception, e:
        stacktrace = traceback.format_exc()
        print stacktrace